#include "bst.h"

void bstree::insert(int val){
        if(root == NULL){
                Node* myNode = new Node(NULL, NULL, NULL, val);
                root = myNode;
        }
        else
                insert(val, root);
}


void bstree::insert(int val, Node* leaf){
        if(val < leaf->val){
                if(leaf->left != NULL)
                        insert(val, leaf->left);
                else{
                        Node* myNode = new Node(leaf, NULL, NULL, val);
                        leaf->left = myNode;
                }
        }
        else{
                if(leaf->right != NULL)
                        insert(val, leaf->right);
                else{
                        Node* myNode = new Node(leaf, NULL, NULL, val);
                        leaf->right = myNode;
                }
        }
}


Node* bstree::search(int val){
        return search(val, root);
}


Node* bstree::search(int val, Node* leaf){
        if(leaf == NULL){
                cout << "not Found!" << endl;
                return (Node*)NULL;
        }
        
        
        if(val < leaf->val)
                return search(val, leaf->left);
        else if(val > leaf->val)
                return search(val, leaf->right);
        else
                return leaf;
}


Node* bstree::find_min(Node* psuedo_root){
        if(psuedo_root->left == NULL)
                return psuedo_root;
        
        return find_min(psuedo_root->left);
}


Node* bstree::find_max(Node* psuedo_root){
        if(psuedo_root->right == NULL)
                return psuedo_root;
        
        return find_max(psuedo_root->right);
}


bool bstree::remove(int val){
        Node* myNode = search(val);
        if(myNode == NULL){
                cout << "Requested node for deletion not found!" << endl;
                return false;
        }
        else
                return remove(myNode);
}


bool bstree::remove(Node* myNode){
        if(myNode == NULL){
                cout << "Requested node for deletion not found!" << endl;
                return false;
        }
        else
        {
                int flag;
                //see which side of its parent the current node belongs to
                if(myNode == myNode->parent->left)
                        flag = 1;
                else
                        flag = 0;
                
                if(myNode->left == NULL && myNode->right == NULL){//leaf
                        cout << "Node-to-delete has no children!" << endl;
                        if(flag == 1)
                                myNode->parent->left = NULL;
                        else
                                myNode->parent->right = NULL;
                        
                        delete myNode;
                        return true;
                }
                
                if(myNode->left == NULL)//only one child
                {
                        if(myNode->parent == NULL)//myNode is root
                        {
                                root = myNode->right;
                                myNode->right->parent = NULL;
                        }
                        else
                        {
                                if(flag == 1)
                                        myNode->parent->left = myNode->right;
                                else
                                        myNode->parent->right = myNode->right;
                                
                                myNode->right->parent = myNode->parent;
                        }
                        delete myNode;
                        return true;
                }
                else if(myNode->right == NULL)//only one child
                {
                        if(myNode->parent == NULL)//myNode is root
                        {
                                root = myNode->left;
                                myNode->left->parent = NULL;
                        }
                        else
                        {
                                if(flag == 1)
                                        myNode->parent->left = myNode->left;
                                else
                                        myNode->parent->right = myNode->left;
                                
                                myNode->left->parent = myNode->parent;
                        }
                        delete myNode;
                        return true;
                }
                else//two children
                {
                        /*
                          Lots can be done here. For example, if we want to
                          balance the tree, we should always swap the
                          max/min node from the left/right subtree (which
                          one has mode levels) with the
                          node-to-delete. note that this is a naive
                          balance strategy.
                        */
                        
                        Node* left_max = find_max(myNode->left);
                        cout << "hoho " << left_max->val << endl;
                        if(left_max != NULL){
                                myNode->val = left_max->val;
                                return remove(left_max);
                                //return true;
                        }
                        
                        Node* right_min = find_min(myNode->right);
                        if(right_min != NULL){
                                myNode->val = right_min->val;
                                return remove(right_min);
                                //return true;
                        }
                        
                        return false;
                }
        }
}


void bstree::destroy(){
        if(root == NULL)
                return;
        
        //method 1 
        destroy(root);
        
        //method 2
        /*
        queue<Node*> myQ;
        myQ.push(root);
        while(!myQ.empty()){
                Node* myNode = myQ.front();
                if(myNode->left != NULL)
                        myQ.push(myNode->left);
                if(myNode->right != NULL)
                        myQ.push(myNode->right);
                delete myNode;
                myQ.pop();
        }
        */
}


void bstree::destroy(Node* leaf){
        if(leaf == NULL)
                return;
        
        destroy(leaf->left);
        destroy(leaf->right);
        delete leaf;
}


void bstree::print(){
        if(root == NULL)
                return;
        
        Node* empty_node = new Node(NULL, NULL, NULL, -1);
        int flag = 0, i = 1, level = 0;
        queue<int> valQ;
        queue<Node*> myQ;
        myQ.push(root);
        valQ.push(root->val);
        while(!myQ.empty()){
                Node* myNode = myQ.front();
                //cout << "haha " << myNode->val << endl;
                if(myNode->left != NULL){
                        flag = 1;
                        myQ.push(myNode->left);
                        valQ.push(myNode->left->val);
                }
                else{
                        myQ.push(empty_node);
                        valQ.push(-1);
                }
                
                if(myNode->right != NULL){
                        flag = 1;
                        myQ.push(myNode->right);
                        valQ.push(myNode->right->val);
                }
                else{
                        myQ.push(empty_node);
                        valQ.push(-1);
                }
                
                if(i == pow(2, level)){
                        if(flag == 1)
                                level++;
                        else{
                                //cout << "hoho" << endl;
                                break;
                        }
                        flag = 0;
                        i = 1;
                }
                else
                        i++;
                
                myQ.pop();
        }

        const int total_level = level;
        cout << "Total level is " << total_level << endl;
        
        i = 1;
        level = 0;
        unsigned int indent = pow(2, (total_level - level)) - 1;
        unsigned int underline_len = pow(2, (total_level - level + 1));
        cout << string(indent, ' ');
        while(!valQ.empty()){
                int val = valQ.front();
                unsigned int interval = pow(2, (total_level - level + 1)) - 1;
                if(val != -1)
                        cout << val << string(interval, ' ');
                else
                        cout << string(interval + 1, ' ');
                if(i == pow(2, level)){
                        cout << endl;
                        cout << string(underline_len, '-') << endl;
                        if(level == total_level)
                                break;
                        level++;
                        if(level != total_level){
                                indent = pow(2, (total_level - level)) - 1;
                                cout << string(indent, ' ');
                        }
                        i = 1;
                }
                else
                        i++;
                valQ.pop();
        }
        
        delete empty_node;
}


int main (int argc, char* argv[]){        
        bstree* BT = new bstree;
        
        BT->insert(10);
        BT->insert(7);
        BT->insert(3);
        BT->insert(13);
        BT->insert(19);
        BT->insert(18);
        BT->insert(1);
        BT->insert(5);
        BT->insert(73);
        BT->insert(31);
        BT->insert(45);
        BT->insert(57);
        BT->insert(63);
        BT->insert(8);
        BT->print();
        
        BT->remove(3);
        BT->remove(13);
        BT->print();
        
        BT->insert(35);
        BT->insert(43);
        BT->insert(33);
        BT->insert(22);
        BT->insert(77);
        BT->insert(13);
        BT->insert(4);
        BT->print();
        
        return 0;
}
